package com.interview.javabasic.Sort;/*
@李子宁
Happy,happy everyday!
冲鸭！
*/

import java.util.Arrays;

public class RedisxSort {
    public static void main(String[] args) {
        int arr[] = {53,3,542,748,14,214};
        redixSort(arr);
    }

    public static void redixSort(int arr[]){
        //首先需要得到最大的数的位数
        int max = arr[0]; //假设第一个数就是最大数
        for (int i = 0; i <arr.length; i++) {
            if (arr[i] > max){
                max = arr[i];
            }
        }
        int[][] bucket = new int[10][arr.length];
        //为了记录每个桶实际存放了多少个数据，定义一个以为数据来记录各个桶
        int[] bucketEleCounts = new int[10];
        int maxLen = (max + "").length();
        for (int i = 0,n=1; i<maxLen;i++,n*=10){
            //定义一个二维数组表示10个桶，每一个桶就是一个二维数组
            //为了防止数据溢出
            for (int j=0; j<arr.length;j++){
                int digitOfElement = arr[j] /n % 10;
                bucket[digitOfElement][bucketEleCounts[digitOfElement]] = arr[j];
                bucketEleCounts[digitOfElement]++;
            }
            //按照桶的顺序放入到数组之中，
            int index = 0;
            //遍历每一个桶，并将桶中的数据放入到数组中
            for (int k=0;k<bucketEleCounts.length;k++){
                //如果桶中有数据，才放入到原数组中
                if (bucketEleCounts[k]!=0){
                    //循环桶，放数据到原数组中
                    for (int l = 0;l<bucketEleCounts[k];l++){
                        arr[index] = bucket[k][l];
                        index++;
                    }
                }
                //每一轮放入后，需要将桶请0
                bucketEleCounts[k]=0;
            }
            System.out.println("第"+(i+1)+"轮处理的结果"+ Arrays.toString(arr));

        }


    }
}
